/*************************************************************************
> File Name: dichotomy.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-14 13:37:39
> Description:
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。
计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，
一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，
并且 至少 有 h 篇论文被引用次数大于等于 h 。
如果 h 有多种可能的值，h 指数 是其中最大的那个。
************************************************************************/

// 思路：
// 我们定义二分查找的左边界 l=0l=0l=0，右边界 r=nr=nr=n。
// 每次我们取 mid=⌊(l+r+1)/2⌋
// 其然后我们统计数组 citations 中大于等于 midmidmid 的元素的个数，记为 s。
// 如果 s≥mids ，说明至少为 mid ,此时我们将左边界变为 mid，否则我们将右边界变为mid−1。
// 当左边界等于右边界时，我们找到了最大的h 值，即为边界值。

#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int hIndex(vector<int> &citations)
    {
        int l = 0, r = citations.size();
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            int s = 0;
            for (int x : citations)
            {
                if (x >= mid)
                {
                    ++s;
                }
            }
            if (s >= mid)
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        return l;
    }
};